package top.minuy.structure.tree.bst;

import top.minuy.structure.linear.array.Array;

import java.util.Random;
/**
 * 二分搜索树的测试类
 *
 * @author Minuy
 * @time 17:59
 * @date 2021/9/9
 */
public class Test {
    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        Integer[] nus = {1,4,2,3,9,5};
        for (Integer i:nus) {
            bst.add(i);
        }
        System.out.println(bst);
        bst.remove(4);
        System.out.println(bst);
        System.out.println("广度优先遍历");
        System.out.println("-> 层序遍历");
        bst.levenOrder();System.out.println();
        System.out.println("深度优先遍历");
        System.out.println("-> 前序遍历（非递归实现）");
        bst.preOrderNr();System.out.println();
        System.out.println("-> 前序遍历");
        bst.preOrder();System.out.println();
        System.out.println("-> 中序遍历");
        bst.inOrder();System.out.println();
        System.out.println("-> 后序遍历");
        bst.postOrder();System.out.println();


        int n = 10000;
        int loopTimes = 10;

        testBst(n, false,true);
        testBst(n, true,true);

        double avgMax = 0;
        double avgMin = 0;

        for (int i=0;i<loopTimes;i++) {
            avgMin += testBst(n, false);
            avgMax += testBst(n, true);
        }
        avgMax/=loopTimes;
        avgMin/=loopTimes;

        System.out.println(String.format("max : %f, min : %f",avgMax,avgMin));
    }

    private static double testBst(int n,boolean isMax){
        return testBst(n,isMax,false);
    }

    private static double testBst(int n,boolean isMax,boolean isShow){
        Random random = new Random();
        BST<Integer> bst= new BST<>();

        if(isShow) {
            System.out.println();
            if (isMax) {
                System.out.println("测试删除最大值");
            } else {
                System.out.println("测试删除最小值");
            }
        }

        for (int i=0;i<n;i++){
            bst.addNr(random.nextInt(n));
        }

        Array<Integer> numbers = new Array<>();

        long startTime = System.nanoTime();
        while (!bst.isEmpty()){
            if(isMax){
                numbers.addLast(bst.removeMax());
            }else {
                numbers.addLast(bst.removeMin());
            }
        }
        long endTime = System.nanoTime();
        if(isShow) {
            System.out.println("检查：");
            System.out.println(numbers.toString());
        }
        boolean check = true;
        for (int i=1;i<numbers.getSize();i++){
            if(isMax){
                if(numbers.get(i-1)<numbers.get(i)){
                    check = false;
                    break;
                }
            }else {
                if(numbers.get(i-1)>numbers.get(i)){
                    check = false;
                    break;
                }
            }
        }
        if(isShow) {
            System.out.println(check);
        }

        if (check){
            return (endTime-startTime)/1000000000.0;
        }else {
            return 1000000000;
        }
    }
}
